The present invention relates to an identification method for use in a multiple access network, a terminal realizing such a method as and an access communication network including such a terminal.
Such a method for use in a multiple access is already known in the art, e.g. from the book xe2x80x9cDigital Communications fundamentals and applicationsxe2x80x9d written by Bernard Sklar and published in 1988 by Prentice Hall/A Division of Simon and Schusterxe2x80x94Englewood Cliffs, N.J. 07632 with ISBN number 0-13-212713-X 025. In chapter 9 xe2x80x9cMultiplexing and Multiple Accessxe2x80x9d and more particularly on page 497 a Demandxe2x80x94Assignment Multiple Access (DAMA) method is described. Contrary to a fixed assignment method where a terminal has periodic access to a common used channel independent of its actual need, a demand-assignment multiple access is a dynamic assignment schemes where a terminal gets access to the common used channel only when it requests access.
One way to impose order in such a method with multiple users having random access requirements is described on page 505 of this chapter. A polling technique is used to poll periodically the different terminals of the access network to determine their service requests. Different kinds of polling techniques are known in the art. In order to explain the present invention a particular one of these polling techniques i.e. anonymous ranging is described hereafter. The anonymous ranging technique defines for each terminal of the access network a unique terminal identifier. This terminal identifier is for instance a unique number, expressed in bits, which is printed by means of a memory in the hardware of the terminal. A so called grant message is distributed on a regular base from a controller of the access network to the different terminals. Such a grant message defines an identifier range which might be defined by e.g. a lower limit terminal identifier and a upper limit terminal identifier. Each terminal desiring access to the network and whereof the terminal identifier falls within this identifier range is allowed to react on the grant message.
However, contention occurs when different terminals are desiring access at the same time and are having an identifier falling within the same identifier range. These terminals are reacting on the same grant message and are creating collision. The anonymous ranging technique continuous then by dividing the identifier range in subranges. Such a subrange is e.g. the half of the identifier range which is defined by the lower limit terminal identifier and a intermediate terminal identifier dividing the previous range into two substantially equal parts. A following grant message defining such a subrange is distributed to the terminals and when identifiers fall within the same subrange, contention occurs again. The searching technique further operates by continually partitioning the population until there is just a single terminal remaining that wants access. At this moment the remaining terminal receives access and the operation is repeated until again a single terminal is yielded in order to receive access to the communication network.
However, if the terminal population is large and the traffic is bursty, the time required to poll the population with a grant message becomes an excessive overhead burden. This will become clear with the following example. Since a company produces and provides a series of terminals with successive identifiers, it is not unlikely that houses in the same neighborhood will end up having a terminal with close identifiers. Imagine two terminals coupled to the same tree of the access network and having identifiers that only differ by one number e.g. the addresses differ only in the least significant bit. After a crash of this tree of the network, all users of this tree will try to log on at nearly the same time. A lot of time is lost since neighbouring terminals with a very similar address try to log on at nearly the same time and congestion occurs up to partitioning of a very low level of the tree. This problem becomes even worse with the growing number of terminals and therewith the growing number of unique identifiers of terminals.
An object of the present invention is to provide an identification method for use in a multiple access communication network, a terminal realizing such a method and an access communication network including such a terminal, such as the above known method but which has not the above drawback of excessive overhead burden and unacceptable identification delay.
According to the invention, this object is achieved by means of the method terminal and access communication network described herein.
The present invention addresses this problem by providing a method which avoids the need to split the identifier range again and again in identifier subranges. The basic idea of the present invention is to compare the result of a reordering of a plurality of elements included in the terminal identifier of the terminal, in a predefined way, by the terminal, with the identifier range in order to decide whether the terminal receives access or not. In this way, the result of the reordering of the elements of neighbouring addresses which would otherwise fall in the same identifier range, will now fall in a different identifier range.
Indeed, reordered neighboring terminal addresses of terminals which desire access at a substantially equal time, will not fall within the same range anymore and will not content for the some grant message anymore. Less grant messages are turned out in contention of terminals with neighboring addresses whereby less time is wasted for each terminal desiring access to the communication network.
A possible implementation of the present invention is described in claim 2 and is illustrated with a quite simple example to make the implementation clear. Presume terminal A and terminal B with the following identifiers in binary notation 00 11 0 and 00 11 1, respectively, which are neighboring identifiers with respect to the value of the identifiers in the decimal notation, value 6 and value 7, respectively. Placing the element positioned on the least significant place with respect to the total value of the identifier to a more significant place with respect to this total value of the identifier can be realized as shown in this example by placing the least significant bit of the binary notation of the identifiers on the third place of the binary notation of the identifiers, and vice versa. The result of the reordering of the neighboring identifiers of terminal A and terminal B becomes 00 01 1 and 00 11 1 with their values in decimal notation value 3 and value 7 respectively. The distance of the value of the reordered neighboring identifiers becomes indeed bigger and therewith the result of comparing these reordered identifiers with an identifier range or subrange becomes different within a shorter delay .
Yet, a very efficient implementation of the present invention is described in claim 3. Indeed, by reversing the elements of neighboring identifiers whereby the element positioned on the least significant place is reordered on the place of the element positioned on the most significant place, reordered neighboring identifiers are falling immediately within a different subrange. This is made clear with the following simple example: the neighboring identifiers AAAB and AAAC with the least significant place and the most significant place positioned on the most right and the most left place of the identifiers, respectively, are both falling within the subrange AAAA up to AEEE; but the inversed neighboring identifiers BAAA and CAAA are immediately falling in different subranges BAAA up to BEEE and CAAA up to CEEE, respectively.
When a terminal identifier is defined by a unique number expressed in bits, the reverse of the identifier is reached by placing the least significant bit on the position of the most significant bit, the second least significant bit on the position of the second most significant bit, . . . , and neighboring terminal identifiers, which only differ from each other with the least significant bit at the end of the sequence of bits, will differ from each other with the most significant bit at the beginning of the sequence of bits.
It should be noted that as is already made clear in the above paragraph with the example of letters, the present invention is not restricted to terminal identifiers which are expressed by a sequence of bits and the present invention is not restricted to reordering of only single elements being one single bit. Indeed, the present invention may be applied to different kind of identifiers with different kinds of representations through different kind of elements as long as an element of an identifier occupies a place or position in the representation of the identifier which assigns a significance to this place in the determination of the value of the identifier determined according to the system wherein the identifier is used. This is shown with the following two examples:
It should further be noticed that the term xe2x80x9cincludingxe2x80x9d, used in the claims, should not be interpreted as being limitative to the means listed thereafter. Thus, the scope of the expression xe2x80x9ca device including means A and Bxe2x80x9d should not be limited to devices consisting only of components A and B. It means that with respect to the present invention, the only relevant components of the device are A and B.
Similarly, it is to be noted that the term xe2x80x9ccoupledxe2x80x9d, also used in the claims, should not be interpreted as being limitative to direct connections only. Thus, the scope of the expression xe2x80x9ca device A coupled to a device Bxe2x80x9d should not be limited to devices or systems wherein an output of device A is directly connected to an input of device B. It means that there exists a path between an output of A and an input of B which may be a path including other devices or means.